package com.lx.algorithm.code.xly3.class03;

import java.util.Arrays;
import java.util.Comparator;
import java.util.Random;
import java.util.TreeMap;

/**
 * Description:
 * Copyright:   Copyright (c)2019
 * Company:     zefu
 *
 * @author: 张李鑫
 * @version: 1.0
 * Create at:   2022-01-04 14:57:57
 * <p>
 * Modification History:
 * Date         Author      Version     Description
 * ------------------------------------------------------------------
 * 2022-01-04     张李鑫                     1.0         1.0 Version
 */
public class Code01 {
    /**
     * 每种工作有难度和报酬，规定如下
     * 给定一个Job类型的数组jobarr，表示所有岗位，每个岗位都可以提供任意份工作
     * 选工作的标准是在难度不超过自身能力值的情况下，选择报酬最高的岗位
     * 给定一个int类型的数组arr，表示所有人的能力
     * 返回int类型的数组，表示每个人按照标准选工作后所能获得的最高报酬
     */

    static class Job {
        public int money;// 该工作的报酬
        public int hard; // 该工作的难度

        @Override
        public String toString() {
            return "Job{" +
                    "money=" + money +
                    ", hard=" + hard +
                    '}';
        }
    }



    public static void sort(Job[] jobs, int l, int r) {
        if (l == r) {
            return;
        }
        int mid = (l + r) / 2;
        sort(jobs, l, mid);
        sort(jobs, mid + 1, r);
        merge(jobs, l, r, mid);
    }

    private static void merge(Job[] jobs, int l, int r, int mid) {
        if (l == r) {
            return;
        }
        int leftIndex = l;
        int rightIndex = mid + 1;
        int L = r - l + 1;
        int arrIndex = 0;
        Job[] arr = new Job[L];

        while (leftIndex <= mid && rightIndex <= r) {
            arr[arrIndex++] = jobs[leftIndex].hard != jobs[rightIndex].hard ?
                    (jobs[leftIndex].hard < jobs[rightIndex].hard ? jobs[leftIndex++] : jobs[rightIndex++]) :
                    (jobs[leftIndex].money > jobs[rightIndex].money ? jobs[leftIndex++] : jobs[rightIndex++]);
        }
        while (leftIndex <= mid) {
            arr[arrIndex++] = jobs[leftIndex++];
        }
        while (rightIndex <= r) {
            arr[arrIndex++] = jobs[rightIndex++];
        }
        arrIndex = 0;
        for (int i = l; i <= r; i++) {
            jobs[i] = arr[arrIndex++];
        }
    }

    public static class JobComparator implements Comparator<Job> {
        @Override
        public int compare(Job o1, Job o2) {
            return o1.hard != o2.hard ? (o1.hard - o2.hard) : (o2.money - o1.money);
        }
    }

    public static int[] maxWages(Job[] jobs, int[] arr) {
        //先排序 难度从小到大 钱从大到小
        sort(jobs, 0, jobs.length - 1);
        TreeMap<Integer, Integer> map = new TreeMap<>();
        Job pre = jobs[0];
        map.put(pre.hard, pre.money);
        for (int i = 1; i < jobs.length; i++) {
            if (jobs[i].hard != pre.hard && jobs[i].money > pre.money) {
                pre = jobs[i];
                map.put(jobs[i].hard, jobs[i].money);
            }
        }
        int[] res = new int[arr.length];

        for (int i = 0; i < arr.length; i++) {
            res[i] = map.floorKey(arr[i]) == null ? 0 : map.get(map.floorKey(arr[i]));
        }
        return res;
    }
    public static int[] getMoneys(Job[] job, int[] ability) {
        Arrays.sort(job, new JobComparator());
        // 难度为key的工作，最优钱数是多少，有序表
        TreeMap<Integer, Integer> map = new TreeMap<>();
        map.put(job[0].hard, job[0].money);
        Job pre = job[0]; // pre 之前组的组长
        for (int i = 1; i < job.length; i++) {
            if (job[i].hard != pre.hard && job[i].money > pre.money) {
                pre = job[i];
                map.put(pre.hard, pre.money);
            }
        }
        int[] ans = new int[ability.length];
        for (int i = 0; i < ability.length; i++) {
            Integer key = map.floorKey(ability[i]);
            ans[i] = key != null ? map.get(key) : 0;
        }
        return ans;
    }


    public static void main(String[] args) {
        Random random = new Random();
        Job[] jobs = new Job[10];
        int[] arr = new int[10];
        for (int i = 0; i < 10; i++) {
            Job job = new Job();
            arr[i] = random.nextInt(10);
            job.money = random.nextInt(100);
            job.hard = random.nextInt(10);
            jobs[i] = job;
        }
        Job[] jobs1 = copyArray(jobs);
        int[] ints = maxWages(jobs1, arr);
        int[] moneys = getMoneys(jobs, arr);
        System.out.println(123);
    }

    public static Job[] copyArray(Job[] arr) {
        if (arr == null) {
            return null;
        }
        Job[] res = new Job[arr.length];
        for (int i = 0; i < arr.length; i++) {
            res[i] = arr[i];
        }
        return res;
    }

}
